1. Field of the Invention
The present invention relates to communication network apparatus such as is used to link together information handling systems or computers of various types and capabilities and to components and methods for data processing in such an apparatus. The present invention includes an improved system and method for frame and protocol classification in an information handling or data processing system. More particularly, the present invention involves routing data packets which can have one of a variety of different protocols by quickly identifying the protocols and providing key information on the packet for use by other portions of the system in further processing data from the packet.
2. Background Art
The description of the present invention which follows is based on a presupposition that the reader has a basic knowledge of network data communications and the routers and switches which are useful in such network communications. In particular, this description presupposes familiarity with the International Standards Organization (xe2x80x9cISOxe2x80x9d) model of network architecture which divides network operation into layers. A typical architecture based on the ISO model extends from a Layer 1 (which is sometimes referred to a xe2x80x9cL1xe2x80x9d) being the physical pathway or media through which signals are passed upward through Layers 2 (or xe2x80x9cL2xe2x80x9d), 3 (or xe2x80x9cL3xe2x80x9d), and so forth to Layer 7 which is the layer of application programming resident in a computer system linked to the network. Throughout this document, references to such layers as L1, L2, L3 are intended to refer to the corresponding layer of the network architecture. The present description also is based on a fundamental understanding of bit strings used in network communication known as packets and frames.
Bandwidth considerations (or the amount of data which a system can handle in a unit of time) are becoming important in today""s view of network operations. Traffic over networks is increasing, both in sheer volume and in the diversity of the traffic. At one time, some networks were used primarily for a certain type of communications traffic, such as voice on a telephone network and digital data over a data transmission network. Of course, in addition to the voice signals, a telephone network would also carry a limited amount of xe2x80x9cdataxe2x80x9d (such as the calling number and the called number, for routing and billing purposes), but the primary use for some networks had, at one point in time, been substantially homogenous packets.
A substantial increase in traffic has occurred as a result of the increasing popularity of the Internet (a public network of loosely linked computers sometimes referred to as the worldwide web or xe2x80x9cwww.xe2x80x9d) and internal analogs of it (sometimes referred to as intranets) found in private data transmission networks. The Internet and intranets involve transmission of large amounts of information between remote locations to satisfy an ever-growing need for remote access to information and emerging applications. The Internet has opened up to a large number of users in geographically dispersed areas an exploding amount of remote information and enabled a variety of new applications, such as e-commerce, which has resulted in a greatly-increased load on networks. Other applications, such as e-mail, file transfer and database access-further add load to networks, some of which are already under strain due to high levels of network traffic.
Voice and data traffic are also converging onto networks at the present time. Data is currently transmitted over the Internet (through the Internet Protocol or IP) at no charge, and voice traffic typically follows the path of lowest cost. Technologies such as voice over IP (VoIP) and voice over asynchronous transfer mode or ATM (VoATM) or voice over frame relay (VoFR) are cost-effective alternatives for transmission of voice traffic in today""s environment. As these services migrate, the industry will be addressing issues such as the changing cost structure and concerns over the trade off between cost of service and quality of service in the transmission of information between processors.
Aspects of quality of service include the capacity or bandwidth (how much information can be accommodated in a period of time), the response time (how long does it take to process a frame) and how flexible is the processing (does it respond to different protocols and frame configurations, such as different encapsulation or frame header methods). Those using a resource will consider the quality of service as well as the cost of service, with the tradeoffs depending on the situation presented.
Some prior art systems which route data packets require that the packets be of a single protocol or format, or one of a limited number of such protocols 6r formats which are permitted. Such a system has advantages of increased speed and responsiveness because of the relative simplicity of the design when packets of only one type of protocol (or a limited number of protocols) are found in the system, since the system can be tailored for that the permitted protocol(s). When the entire data transmission system was under the control of a single entity, it was easy for the controlling entity to enforce a single standard transmission protocol on users (either users followed the permitted protocol(s) or didn""t use the network, because the network was programmed to accommodate only the specified protocol(s) and could not handle variations in the protocols, even seemingly minor variations).
However, frames from even a communications xe2x80x9cstandardxe2x80x9d like Ethernet can be formatted using one of several protocols and can be encapsulated into a message using different encapsulation techniques. These different protocols and encapsulation technique provide a varying amount of data, typically at the beginning of a frame and before other key information such as the beginning of the L3 message. Thus, key information from an Ethernet frame can be located in different places within the frame, depending on the Ethernet L3 protocol or form of Ethernet and the encapsulation technique, if one is present. A system which provides processing of the L3 message needs to find it first, and that can be a challenge in a multi-protocol system. So, for example, Ethernet DIX Version 2 differs from Ethernet 802.3, IPX over Ethernet differs from IPX over Ethernet 802.3 which itself has three different formats (Novell Proprietary, LLC and SNAP). Further, each version of IPX may or may not support a virtual LAN (or VLAN) using the so-called IEEE 802.1q standard, which also has the effect of changing the format of the frame, and thus the location of the L3 message.
In those prior systems in which frames in a multitude of protocols were supported, it was sometimes necessary to provide a significant amount of overhead (such as computer programming sometimes including more than one hundred lines of code with comparisons and branching instructions) to identify the protocol and to translate a frame from one protocol to another, or to remove unnecessary information (such as encapsulation information) from a frame. Such multiple protocol processing was also time consuming to use these prior systems of translation techniques, and further, it took a variable amount of time to identify the protocol using software techniques. When such systems required a variable amount of time to identify the protocol and provide the necessary processing, the system would have to be configured to allow the longest time necessary (to handle the worst case), slowing down the processing of all frames to the worst case or having the possibility that some frames would not be processed in the time allowed for categorization.
Most processors start processing from a common beginning of an instruction set (the same place for all data) and set flags which the processor reads selectively when it needs to determine where to go and which instructions to execute. Thus, the execution of many processors performs a number of tests to determine what kind of data it has and where to begin the substantive processing, tests which involve a number of cycles and could involve a lot of processing.
Thus, the prior art systems for handling data packets had undesirable disadvantages and limitations which had an effect either on the versatility of the system or the speed with which it could operate.
The present invention overcomes the disadvantages and limitations of the prior art systems by providing a simple, yet effective, way of handling frames or packets which were created using one of a plurality of different permitted message protocols and which may or may not employ a virtual local area network (or VLAN) system. By analyzing each packet or frame in a quick and efficient manner, the type of frame and key characteristics of the frame can be determined and saved for future reference and processing regarding that frame, for example, in a network processor of the type described in the NPU Patent referenced above.
It is an advantage of the present invention that it is quick and efficient in the handling of packets having different protocols and provides for faster and easier processing of the packets, allowing the entire system to operate at a high rate of frame processing.
The present invention allows a router or switch to process successive packets or frames in varying formats without knowing in advance in what format the particular frame or packet was created. This invention includes identifying the layer 2 (L2) encapsulation format of the message or packet and then applying stored rules to identify the L2 encapsulation, the L3 protocol and the presence of a virtual local area network (VLAN). As a result of such determination, the processor is ready to run at a starting instruction address; that is, the processor is preconditioned with the instruction""s starting address which is based on the identification of the frame. The processor thus has a starting instruction address as well as a pointer to the beginning of the L3 header in the data portion of the frame as well as flags indicating the protocol, VLAN presence and the encapsulation format.
The present invention has the advantage that it sets up and stores key information about a packet during the initial processing of the packet, then that stored information about the packet or frame can be used later in the processing to advantage, allowing quicker and more efficient processing of the packet in its later stages, for example, by network processing unit complexes described in the NPU Patent. This key information includes, in the preferred embodiment, the beginning location of the L3 message and the starting address in the instruction set for processing the frame.
The present invention contemplates that it can be implemented on the same semiconductor substrate as an array of network processor and their associated storage components, allowing for fast data transmission between the components.
The present invention also has the advantage that it can be implemented in hardware, rather than software, and that the tests can be completed in a uniform time regardless of the format and how many comparisons must be made before the format or encapsulation techniques is determined. In the design shown, within two cycles of the clock, the classification of a frame can be completed, with the necessary indicators set to indicate what kind of a frame is present (e.g., what encapsulation technique and what layer 3 protocol were used) and whether a virtual LAN (or VLAN) is supported as well as key information about the frame. During the same two cycles, a frame can be routed by a dispatcher to an idle network processing unit (as described in the referenced NPU Patent). As a result of the processing of the frame to determine the protocol and encapsulation method, a starting address for the processor can be determined and passed to the processor so that the processor can begin its work on the frame, pre-loaded with the starting address (a pointer to the relevant instruction storage) and other relevant information for its processing. This pre-loading of the processor with a starting address for processing is sometimes referred to as preconditioning of the processor and enables processor efficiencyxe2x80x94it need not go through a number of test instructions and jump instructions based on the results of the test, but instead starts at the initial address for the particular format of message presented.
The system of the present invention also has the advantage that the classification and preprocessing of a frame can occur in parallel with the distribution of that frame to a network processing complex. This parallel processing allows for more efficient handling of frames and allows the system to operate faster.
One enhancement to the present invention allows not only the preconditioning of the processor (storing the address of the first instruction) but also storing of additional address of instructions for later execution. In this way, the processor has the address of the first instruction and also the address for instructions at later branch (or fork) points, avoiding unnecessary testing (if condition, then go to instruction #1 otherwise go to instruction #2) in the execution of the code. This allows the code to execute more efficiently.